【考试总结】 Test-2019.3.28 HNOI2019模拟 | Qiuly's blog!

【考试总结】 Test-2019.3.28 HNOI2019模拟

Posted on | Edited on | In | Comments:

今天的题目貌似暴力分好拿写欸，然而……窝只有 $70$ ？不过排名比昨天上升了什么鬼。

$QwQ$ 题目的确很难懂，所以窝听了讲解后也没听懂多少，不过还是改出了第一题(第一题是人就改的出好吧o(≧口≦)o)。

题目压缩包戳我!!!~\(≧▽≦)/~(有时链接可能会崩，如果崩了的话请稍后尝试QwQ)

T1

期望得分：30分
实际得分：30分
正解：找规律??
窝的解法：暴力模拟题意

题解：

第一眼看到题目，欸，如果按照题面模拟就有 $30$ 分！出题人良心啊。然后看数据范围，$100\%$ 的数据的 $n\leq 3\times10^7$ ，这应该是 $O(n)$ 算法才行啊，于是想，或许是线性 $DP$ ，然后推式子，推出这么一个鬼玩意：

$sum(a[i])$ 就是在 $1$ 到 $i-1$ 中大于 $a[i]$ 的数的个数，然后 $f[i]$ 表示将前 $i$ 个元素进行冒泡需要的交换次数。

很显然这是错的。

然后我就想到了 $NOI$ 往年的冒泡排序(貌似是 $NOI$ 的?)，其实两道题没什么联系。

哎好吧发现过不去直接上暴力吧，题目说什么就做什么，于是把我用来对拍的暴力程序提交了上去，$30$ 分。

接下来讲讲正解。

很显然，对于一个元素 $a_i$ ，它所在的位置为 $i$ ，然而最后排好序后 $ta$ 应该回到的位置为 $a_i$ 。观察冒泡过程，发现对于一个元素，每次冒泡排序都最多会将 $ta$ 向自己的目标位置移动一格。

然后就是，比如说当前序列的最小元素，假设最小元素的起点位置为 $s$ ,我们发现每次冒泡总会将 $ta$ 向前移一格，然后在第 $s-1$ 次冒泡排序的时候 $1$ 归位了。然后发现 $1$ 的移动对 $2$ 的移动次数并没有产生影响，这个时候将 $1$ 删去，发现 $2$ 归位的移动次数变成了 $2$ 的初始位置 $-$ $1$ ，放在原序列中就是 $2$ 的初始位置 $-$ $2$ 。

这至少说明，对于任意一个元素 $i$ ，其所需要的移动次数为 $i-a_i$ 。

那么，如果要使序列有序，所需要的排序次数就是 $max\{ i-a_i \}$ 。直接计算答案即可。

(实际上窝也不是很明白…..貌似是这样的吧 $QwQ$ )

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,S,B,C,D,A[10006];
int main() {
    freopen("magician.in","r",stdin);
    freopen("magician.out","w",stdout);
    scanf("%d%d%d%d%d",&n,&S,&B,&C,&D);
    for(int i=1;i<=n;++i) {
        A[i]=i;
        S=(S*B+C)%D;
        swap(A[i],A[(S%i)+1]);
    }
    int counter=0;
    for(int i=1;i<=n;++i)counter=max(counter,i-A[i]);
    printf("%d\n",counter);
    return 0;
}

T2

期望得分：30分
实际得分：0分
正解：容斥+搜索+剪枝
窝的解法：暴搜

题解：

不会………….然后暴搜打挂了没得分。

所以这不能说是题解，留个坑吧。

T3

期望得分：40分
实际得分：40分
正解：将所有颜色维护成链，然后分块加速
窝的解法：直接维护成链

对于一个 $i$ ，如果 $a_i=k$ ，并且 $a_j=k$ ，而且 $i$ 和 $j$ 是离得最近的，则将它们向前向星那样连起来，最后对询问的区间直接暴力跳即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <map>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=5e5+7;
const int LogN=27;

vector<int> seq;
map<int,int> hashs;

int n,q,a[N],head[N],nxt[N],f[LogN+7][N],logs[N],ans;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

inline void pre_st(){
    logs[0]=-1;
    for(int i=1;i<=n;++i)logs[i]=logs[i>>1]+1;
    for(int i=1;i<=n;++i)f[0][i]=a[i];
    for(int t=1;t<LogN;++t)
        for(int i=1;i<=n;++i)
            if(i+(1<<t)-1<=n)
                f[t][i]=max(f[t-1][i],f[t-1][i+(1<<(t-1))]);
} 
inline int query(int x,int y){
    int t=logs[y-x+1];
    return max(f[t][x],f[t][y-(1<<t)+1]);
}
 
inline void solve(int x,int lim) {
    for(int now=x,last=nxt[x];last>=lim;last=nxt[last]) {
        while(now>last&&query(last,now)>a[last]) now=nxt[now];
        ans=max(ans,now-last+1);
    }
}
 
inline void make_hashs() {
	sort(seq.begin(),seq.end());
    seq.erase(unique(seq.begin(),seq.end()),seq.end());
    for(int i=0;i<seq.size();++i) hashs[seq[i]]=i+1;
    for(int i=1;i<=n;++i) a[i]=hashs[a[i]];
    memset(head,-1,sizeof head);
}

int main() {
	freopen("spiral.in","r",stdin);
	freopen("spiral.out","w",stdout);
    IN(n),IN(q);
    for(int i=1;i<=n;++i)
        IN(a[i]),seq.push_back(a[i]);
    make_hashs();
    for(int i=1;i<=n;++i)
        nxt[i]=head[a[i]],head[a[i]]=i;
    pre_st();
    while(q--) {
        ans=1;
		int x,y;IN(x),IN(y);
        for(int i=y;i>=x;--i) solve(i,x);
        printf("%d\n",ans);
    }
    return 0;
}

正解不费………………………………….

本文标题:【考试总结】 Test-2019.3.28 HNOI2019模拟

文章作者:Qiuly

发布时间:2019年03月28日 - 00:00

最后更新:2019年04月03日 - 17:32

原始链接:http://qiulyblog.github.io/2019/03/28/[考试总结]test20190328/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。